import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.concurrent.DelayQueue;
import java.util.stream.Collectors;

/**
 * @author ZhengDp
 * @Date 2023/4/22 22:13
 */
public class 高级搜索 {

    /*
    * #problem 773 滑动谜题
    * */
    @Test
    void test(){
        slidingPuzzle(new int[][]{
                {4,1,2},{5,0,3}
        });
    }
    private int[][] moves = new int[][]{
            {1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}
    };
    // 1. BFS
    public int slidingPuzzle(int[][] board) {
        String end = "123450";
        String begin = Arrays.stream(board).map(item -> {
            return Arrays.stream(item).mapToObj(item1 -> String.valueOf(item1)).collect(Collectors.joining());
        }).collect(Collectors.joining());
        if(begin.equals(end)) {
            return 0;
        }
        Deque<String> q = new LinkedList<>();
        q.offer(begin);
        Set<String> dict = new HashSet<>();
        dict.add(begin);
        int step = 0;
        while(!q.isEmpty()) {
            int sz = q.size();
            step++;
            while(sz -- > 0) {
                char[] now = q.poll().toCharArray();
                int i =0;
                for(;i<now.length;i++) {
                    if(now[i] == '0'){
                        break;
                    }
                }
                char origin = now[i];
                for(int j : moves[i]) {
                    char t = now[j];
                    now[j] = now[i];
                    now[i] = t;
                    String next = String.valueOf(now);
                    now[i] = origin;
                    now[j] = t;
                    if(dict.contains(next)) {
                        continue;
                    }
                    if(next.equals(end)) {
                        return step;
                    }
                    q.offer(next);
                    dict.add(next);

                }
            }
        }

        return -1;
    }

    //2. A* + BFS
    class Node1 {
        String str;
        int x, y;
        int val;
        Node1(String _str, int _x, int _y, int _val) {
            str = _str; x = _x; y = _y; val = _val;
        }
    }
    int f(String str) {
        int ans = 0;
        char[] cs1 = str.toCharArray(), cs2 = e.toCharArray();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 跳过「空格」，计算其余数值的曼哈顿距离
                if (cs1[i * m + j] == '0' || cs2[i * m + j] == '0') continue;
                int cur = cs1[i * m + j], next = cs2[i * m + j];
                int xd = Math.abs((cur - 1) / 3 - (next - 1) / 3);
                int yd = Math.abs((cur - 1) % 3 - (next - 1) % 3);
                ans += (xd + yd);
            }
        }
        return ans;
    }
    int n = 2, m = 3;
    String s, e;
    int x, y;
    public int slidingPuzzle2(int[][] board) {
        s = "";
        e = "123450";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                s += board[i][j];
                if (board[i][j] == 0) {
                    x = i; y = j;
                }
            }
        }

        // 提前判断无解情况
        if (!check(s)) return -1;

        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        Node1 root = new Node1(s, x, y, f(s));
        PriorityQueue<Node1> q = new PriorityQueue<>((a,b)->a.val-b.val);
        Map<String, Integer> map = new HashMap<>();
        q.add(root);
        map.put(s, 0);
        while (!q.isEmpty()) {
            Node1 poll = q.poll();
            int step = map.get(poll.str);
            if (poll.str.equals(e)) return step;
            int dx = poll.x, dy = poll.y;
            for (int[] di : dirs) {
                int nx = dx + di[0], ny = dy + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                String nStr = update(poll.str, dx, dy, nx, ny);
                if (!map.containsKey(nStr) || map.get(nStr) > step + 1) {
                    Node1 next = new Node1(nStr, nx, ny, step + 1 + f(nStr));
                    q.add(next);
                    map.put(nStr, step + 1);
                }
            }
        }
        return 0x3f3f3f3f; // never
    }
    String update(String cur, int i, int j, int p, int q) {
        char[] cs = cur.toCharArray();
        char tmp = cs[i * m + j];
        cs[i * m + j] = cs[p * m + q];
        cs[p * m + q] = tmp;
        return String.valueOf(cs);
    }
    boolean check(String str) {
        char[] cs = str.toCharArray();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n * m; i++) {
            if (cs[i] != '0') list.add(cs[i] - '0');
        }
        int cnt = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i) > list.get(j)) cnt++;
            }
        }
        return cnt % 2 == 0;
    }

    /*
     * #problem 1091 二进制矩阵中的最短路径
     * */
    private int min = Integer.MAX_VALUE;
    private int[][] directs = new int[][]{
            {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}
    };

    // 1. 回溯 + 剪枝 --> 超时
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) {
            return -1;
        }
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        visited[0][0] = true;
        shortestPathBinaryMatrixDFS(grid, 0, 0, 1, visited);
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private void shortestPathBinaryMatrixDFS(int[][] grid, int x, int y, int step, boolean[][] visited) {
        if (x == grid.length - 1 && y == grid[0].length - 1) {
            min = Math.min(min, step);
            return;
        }
        for (int i = 0; i < 8; i++) {
            int tx = x + directs[i][0];
            int ty = y + directs[i][1];
            if (tx < 0 || ty < 0 || tx >= grid.length || ty >= grid[0].length || grid[tx][ty] != 0 || visited[tx][ty]) {
                continue;
            }
            visited[tx][ty] = true;
            shortestPathBinaryMatrixDFS(grid, tx, ty, step + 1, visited);
            visited[tx][ty] = false;
        }
    }


    // 2. BFS + 启发式函数 （A*Search)
    public int shortestPathBinaryMatrix2(int[][] grid) {
        if (grid[0][0] == 1) {
            return -1;
        }
        int n = grid.length;
        if (n == 1) {
            return grid[0][0] == 1 ? -1 : 1;
        }
        PriorityQueue<Node> q = new PriorityQueue<>(10, (o1, o2) -> {
            if(o1.step != o2.step) {
                return o1.step - o2.step;
            } else {
                return distance(o1.x,o1.y,n-1) - distance(o2.x,o2.y,n-1);
            }
        });
        Node start = new Node(0, 0, 1);
        boolean[][] visited = new boolean[n][n];
        q.offer(start);
        visited[0][0] = true;
        while (!q.isEmpty()) {
            Node cur = q.poll();
            int x = cur.x, y = cur.y;
            if(x == n-1 && y == n-1) {
                return cur.step;
            }
            for (int[] direct : directs) {
                int tx = x + direct[0];
                int ty = y + direct[1];
                if (isBound(tx, ty, n, n) && !visited[tx][ty] && grid[tx][ty] == 0) {
                    Node newNode = new Node(tx, ty, cur.step+1);
                    q.offer(newNode);
                    visited[tx][ty] = true;
                }
            }
        }
        return -1;
    }

    private boolean isBound(int x, int y, int n, int m) {
        return x >= 0 && y >= 0 && x < n && y < m;
    }

    private class Node {
        public int x;
        public int y;
        public int step;

        public Node(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }

    private int distance(int x, int y, int n) {
        return (n-x) + (n-y);
    }

    // 3. 直接BFS
    public int shortestPathBinaryMatrix3(int[][] grid) {
        int n = grid.length;
        if(grid[0][0] == 1) {
            return -1;
        }
        Deque<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0});
        grid[0][0] = 1;
        int step = 0;
        while(!q.isEmpty()) {
            int sz = q.size();
            step++;
            while(sz -- > 0) {
                int[] poll = q.poll();
                int x = poll[0];
                int y = poll[1];

                if(x == n-1 && y == n-1) {
                    return step;
                }
                for(int[] direct : directs) {
                    int tx = x + direct[0];
                    int ty = y + direct[1];
                    if(isBound(tx,ty,n,n) && grid[tx][ty] == 0) {
                        q.offer(new int[]{tx,ty});
                        grid[tx][ty] = 1;
                    }
                }
            }
        }
        return -1;
    }


    /*
     * #problem 433 最小基因变化
     * */
    // 1. 同单词接龙 -- 双向BFS
    public int minMutation(String startGene, String endGene, String[] bank) {
        if (startGene.equals(endGene)) {
            return 0;
        }
        Set<String> dict = new HashSet<>(Arrays.asList(bank));
        if (!dict.contains(endGene)) {
            return -1;
        }
        dict.add(startGene);
        Deque<String> q1 = new LinkedList<>(), q2 = new LinkedList<>();
        Set<String> m1 = new HashSet<>(), m2 = new HashSet<>();
        q1.offer(startGene);
        q2.offer(endGene);
        m1.add(startGene);
        m2.add(endGene);
        int step = 0;
        Deque<String> q = null;
        Set<String> cur = null, other = null;
        while (!q1.isEmpty() && !q2.isEmpty()) {
            if (q1.size() <= q2.size()) {
                q = q1;
                cur = m1;
                other = m2;
            } else {
                q = q2;
                cur = m2;
                other = m1;
            }
            int sz = q.size();
            step++;
            while (sz-- > 0) {
                String curGene = q.poll();
                char[] arr = curGene.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    char origin = arr[i];
                    for (char c = 'A'; c <= 'Z'; c++) {
                        arr[i] = c;
                        String nextWord = String.valueOf(arr);
                        if (cur.contains(nextWord) || !dict.contains(nextWord)) {
                            continue;
                        }
                        if (other.contains(nextWord)) {
                            return step;
                        }
                        q.offer(nextWord);
                        cur.add(nextWord);
                    }
                    arr[i] = origin;
                }
            }
        }

        return -1;
    }

    /*
     * #problem 127 单词接龙
     * */
    // 1. 双向BFS 减少搜索空间爆炸问题
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) {
            return 1;
        }
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }
        Deque<String> q1 = new LinkedList<>(), q2 = new LinkedList<>();
        Set<String> m1 = new HashSet<>(), m2 = new HashSet<>();
        q1.offer(beginWord);
        q2.offer(endWord);
        m1.add(beginWord);
        m2.add(endWord);
        dict.add(beginWord);
        Deque<String> queue = null;
        Set<String> cur = null;
        Set<String> other = null;
        int step = 1;
        while (!q1.isEmpty() && !q2.isEmpty()) {
            if (q1.size() <= q2.size()) {
                queue = q1;
                cur = m1;
                other = m2;
            } else {
                queue = q2;
                cur = m2;
                other = m1;
            }
            int sz = queue.size();
            step++;
            while (sz-- > 0) {
                String curWord = queue.poll();
                char[] arr = curWord.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    char origin = arr[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        arr[i] = c;
                        String nextWord = String.valueOf(arr);
                        if (cur.contains(nextWord) || !dict.contains(nextWord)) {
                            continue;
                        }
                        if (other.contains(nextWord)) {
                            return step;
                        }
                        queue.offer(nextWord);
                        cur.add(nextWord);
                    }
                    arr[i] = origin;
                }
            }
        }
        return 0;
    }

    /*
     * #problem 70 爬楼梯
     * */
    // 1. 回溯+剪枝（记忆化搜索）
    public int climbStairs(int n) {
        return climbStairs(n, new int[n + 1]);
    }

    private int climbStairs(int n, int[] memo) {
        if (n < 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
        return memo[n];
    }

    /*
     * #problem 22 括号生成
     * */
    // 1. DFS + 剪枝
    public List<String> generateParenthesis(int n) {
        return generateParenthesisDfs(n, 0, 0, "");
    }

    private List<String> generateParenthesisDfs(int n, int left, int right, String temp) {
        if (temp.length() == 2 * n) {
            return new ArrayList<>(Arrays.asList(temp));
        }
        List<String> res = new ArrayList<>();
        if (left < n) {
            res.addAll(generateParenthesisDfs(n, left + 1, right, temp + "("));
        }
        if (right < left) {
            res.addAll(generateParenthesisDfs(n, left, right + 1, temp + ")"));
        }
        return res;
    }

    /*
     * #problem 51 N皇后
     * */
    // 1. 回溯+剪枝（去掉错误的分支）
    private List<List<String>> NQRes = new ArrayList<>();
    private List<String> temp = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        // 行/列/斜杠不能 同时存在Queen
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append('.');
        }
        List<String> situation = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            sb.setCharAt(i, 'Q');
            situation.add(sb.toString());
            sb.setCharAt(i, '.');
        }
        solveNQueensDfs(n, 0, situation, new HashSet<>(), new HashSet<>(), new HashSet<>());
        return NQRes;
    }

    private void solveNQueensDfs(int n, int x, List<String> situation, Set<Integer> d1, Set<Integer> d2, Set<Integer> lines) {
        if (temp.size() == n) {
            NQRes.add(new ArrayList<>(temp));
            return;
        }
        for (int y = 0; y < n; y++) {
            if (lines.contains(y) || d1.contains(x - y) || d2.contains(x + y)) {
                continue;
            }
            temp.add(situation.get(y));
            lines.add(y);
            d1.add(x - y);
            d2.add(x + y);
            solveNQueensDfs(n, x + 1, situation, d1, d2, lines);
            temp.remove(temp.size() - 1);
            lines.remove(y);
            d1.remove(x - y);
            d2.remove(x + y);
        }
    }

    /*
     * #problem 37 解数独
     * */
    // 1. DFS 在填充数的过程中保证填充的数字是正确的
    /*
     * 利用返回的状态值来判断是否需要进行状态回溯（如果返回true，说明得到了正确结果，就不需要进行状态的重置）
     * */
    public void solveSudoku(char[][] board) {
        int[][] rows = new int[9][10];
        int[][] cols = new int[9][10];
        int[][] subBox = new int[9][10];
        for (int x = 0; x < 9; x++) {
            for (int y = 0; y < 9; y++) {
                if (board[x][y] == '.') {
                    continue;
                }
                int num = board[x][y] - '0';
                int boxNum = (x / 3) * 3 + y / 3;
                rows[x][num]++;
                cols[y][num]++;
                subBox[boxNum][num]++;
            }
        }
        solveSudokuDFS(board, 0, rows, cols, subBox);
    }

    private boolean solveSudokuDFS(char[][] board, int pos, int[][] rows, int[][] cols, int[][] subBox) {
        int x = pos / board[0].length, y = pos % board[0].length;
        if (x >= board.length || y >= board[0].length) {
            return true;
        }
        if (board[x][y] != '.') {
            return solveSudokuDFS(board, pos + 1, rows, cols, subBox);
        } else {
            int subBoxNum = (x / 3) * 3 + y / 3;
            for (int i = 1; i <= 9; i++) {
                if (rows[x][i] != 0 || cols[y][i] != 0 || subBox[subBoxNum][i] != 0) {
                    continue;
                }
                rows[x][i]++;
                cols[y][i]++;
                subBox[subBoxNum][i]++;
                board[x][y] = (char) ('0' + i);
                if (solveSudokuDFS(board, pos + 1, rows, cols, subBox)) {
                    return true;
                }
                rows[x][i]--;
                cols[y][i]--;
                subBox[subBoxNum][i]--;
            }
            board[x][y] = '.';
        }
        return false;

    }

    /*
     * #problem 36 有效的数独
     * 关键点在于如何区分 各个区域块
     * */
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][10];
        int[][] cols = new int[9][10];
        int[][] subBox = new int[9][10];
        for (int x = 0; x < 9; x++) {
            for (int y = 0; y < 9; y++) {
                if (board[x][y] == '.') {
                    continue;
                }
                int num = board[x][y] - '0';
                int boxNum = (x / 3) * 3 + y / 3;
                rows[x][num]++;
                cols[y][num]++;
                subBox[boxNum][num]++;
                if (rows[x][num] > 1 || cols[y][num] > 1 || subBox[boxNum][num] > 1) {
                    return false;
                }
            }
        }

        return true;
    }
}
